package code.daily;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author 26029
 * @date 2025/4/25
 * @description 抽象好题
 */
public class AbstractCode {
    // 407. 接雨水 II
    public int trapRainWater(int[][] heightMap) {
        // 构建最小堆
        int m = heightMap.length, n = heightMap[0].length;
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<Node407> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.height));
        // 加入四周边界
        for (int i = 0; i < m; i++) {
            queue.offer(new Node407(i, 0, heightMap[i][0]));
            queue.offer(new Node407(i, n - 1, heightMap[i][n - 1]));
            visited[i][0] = true;
            visited[i][n - 1] = true;
        }
        for (int j = 1; j < n - 1; j++) {
            queue.offer(new Node407(0, j, heightMap[0][j]));
            queue.offer(new Node407(m - 1, j, heightMap[m - 1][j]));
            visited[0][j] = true;
            visited[m - 1][j] = true;
        }
        // 遍历
        int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int ans = 0;
        while (!queue.isEmpty()) {
            Node407 temp = queue.poll();
            int i = temp.i, j = temp.j, height = temp.height;
            for (int[] d : dir) {
                int x = i + d[0], y = j + d[1];
                if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y])
                    continue;
                // 得到这个节点
                int newHeight = heightMap[x][y];
                // 如果新节点比这个节点高，那么舍弃原节点，加入新节点；如果新节点矮，那么答案补上这些水，加入新节点
                if (newHeight < height)
                    ans += height - newHeight;
                queue.add(new Node407(x, y, Math.max(height, newHeight)));
                visited[x][y] = true;
            }
        }

        return ans;
    }

    static class Node407 {
        int i, j;
        int height;
        public Node407(int i, int j, int height) {
            this.i = i;
            this.j = j;
            this.height = height;
        }
    }

    // 42. 接雨水
    public int trap(int[] height) {
        int len = height.length;
        int ans = 0;
        boolean[] visited = new boolean[len];
        visited[0] = true;
        visited[len - 1] = true;
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[0], o2[0]));
        queue.add(new int[]{height[0], 0});
        queue.add(new int[]{height[len - 1], len - 1});
        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            int h = temp[0], pos = temp[1];
            if (pos + 1 < len && !visited[pos + 1]) {
                int newH = height[pos + 1];
                if (newH < h)
                    ans += h - newH;
                queue.add(new int[]{Math.max(h, newH), pos + 1});
                visited[pos + 1] = true;
            }
            if (pos - 1 >= 0 && !visited[pos - 1]) {
                int newH = height[pos - 1];
                if (newH < h)
                    ans += h - newH;
                queue.add(new int[]{Math.max(h, newH), pos - 1});
                visited[pos - 1] = true;
            }
        }
        return ans;
    }
}
